package com.lh.demo;

import java.util.Arrays;

/**
 * @author: linghao
 * @since: 2023/2/9
 *
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
 * 换句话说，第一个字符串的排列之一是第二个字符串的 子串
 *
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 *
 * 参考：字符串的排列NC121算法(递归+回溯)，用这个方法字符串长的话。递归很深，很慢，内存不够用，不合适
 */
public class 剑指OfferII014字符串中的变位词滑动 {

    public static void main(String[] args) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        ++cnt1['c' - 'a'];
        ++cnt2['d' - 'a'];
        System.out.println();
    }

    //滑动窗口  leetcode,将s2拆解为若干个和S1长度相同的字符
    //两个数组中字符的个数相同时 为true
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(),m = s2.length();
        if(n>m) return false;
        int[] cnt1  = new int[26];
        int[] cnt2  = new int[26];

        for(int i=0;i<n;i++){
            ++cnt1[s1.charAt(i)-'a'];
            ++cnt2[s2.charAt(i)-'a'];
        }
        if(Arrays.equals(cnt1,cnt2))return true;
        //开始滑动窗口，前面进一个，后面出去一个
        for(int i=n;i<m;i++){
            ++cnt2[s2.charAt(i)-'a'];
            --cnt2[s2.charAt(i - n)-'a'];
            if(Arrays.equals(cnt1,cnt2))return true;
        }
        return false;
    }
}
